package com.platform.modules.alg.alglib.poj3104;

import java.util.Arrays;

public class Poj3104 {
    private int n;
    private int k;
    private Integer a[] = new Integer[100005];
    private String output = "";

    public Poj3104() {
        for (int i = 0; i < a.length; i++) {
            a[i] = 0xFFFFF;
        }
    }

    boolean judge(int x) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] > x)
                sum += (a[i] - x + k - 2) / (k - 1); // 上取整
            if (sum > x)
                return false;
        }
        return true;
    }

    void solve() {
        Integer l = 1, r = a[n - 1], ans = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (judge(mid)) {
                ans = mid;
                r = mid - 1; // 减小
            } else
                l = mid + 1; // 增大
        }
        output += ans.toString();
        output += "\n";
    }

    public String cal(String input) {
        String[] line = input.split("\n");
        n = Integer.parseInt(line[0]);
        String[] words = line[1].split(" ");

        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(words[i]);
        }
        Arrays.sort(a, 0, n - 1);
        k = Integer.parseInt(line[2]);
        if (k == 1) {
            output += a[n - 1].toString();
            output += "\n";
        }

        solve();
        return output;
    }
}
